<head>
    <meta charset="UTF-8">
<title>算法训练 Flights</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>LiLand 是一个国家，包含 <i>n</i> 个城市。城市的编号从 1 到 <i>n</i>。这个国家因为它的非常奇怪的交通运输系统而闻名。这里有许多单向的航班让你可以在两个城市之间旅行，但是这些航班的安排使得你一旦离开一个城市就永远不会再回来了。</p>
<p>在以前，每趟航班恰好飞行一个小时，但是最近由于 Lily 成为了交通运输系统的新经理，她想要改变一些航班的飞行时间。具体来说，她想要把某些航班的飞行时间改为 2 小时，使得所有从 1 号城市到 <i>n</i> 号城市的旅行路线都花费相同的时间。</p>
<p>【输入格式】</p>
<p>输入数据的第一行包含两个整数 <i>n</i> 和 <i>m</i>，表示城市的数量和航班的数量。</p>
<p>接下来 <i>m</i> 行，每行包含两个整数 <i>a<sub>i</sub></i> 和 <i>b<sub>i</sub></i> (1 &le; <i>a<sub>i</sub></i> &lt; <i>b<sub>i</sub></i> &le; <i>n</i>)，表示城市 <i>a<sub>i</sub></i> 到城市 <i>b<sub>i</sub></i> 有一趟单向航班。数据保证存在至少一条从城市1到城市 <i>n</i> 的路径，且航班不会形成环，任意两个城市之间不会有多趟航班。</p>
<p>【输出格式】</p>
<p>如果不能满足 Lily 的要求，只输出一行&quot;No&quot;(不包含引号)。</p>
<p>否则，第一行输出&quot;Yes&quot;(不包含引号)，接下来的 <i>m</i> 行，每行输出一个整数 <i>ans<sub>i</sub></i> (1 &le; <i>ans<sub>i</sub></i> &le; 2)，表示每条航班新的飞行时间。你的输出顺序需要与输入的航班顺序相符。</p>
<p>如果有多解，输出任意一种即可。</p>
<p>【样例输入】</p>
<p>3 3</p>
<p>1 2</p>
<p>2 3</p>
<p>1 3</p>
<p>【样例输出】</p>
<p>Yes</p>
<p>1</p>
<p>1</p>
<p>2</p>
<p>【样例输入】</p>
<p>4 4</p>
<p>1 2</p>
<p>2 3</p>
<p>3 4</p>
<p>1 4</p>
<p>【样例输出】</p>
<p>No</p>
<p>【样例输入】</p>
<p>5 6</p>
<p>1 2</p>
<p>2 3</p>
<p>3 5</p>
<p>1 4</p>
<p>4 5</p>
<p>1 3</p>
<p>【样例输出】</p>
<p>Yes</p>
<p>1</p>
<p>1</p>
<p>1</p>
<p>2</p>
<p>1</p>
<p>2</p>
<p>【数据规模和约定】</p>
<p>对于20%的数据，2 &le; <i>n</i> &le; 10，1 &le; <i>m</i> &le; 20；</p>
<p>对于60%的数据，2 &le; <i>n</i> &le; 100，1 &le; <i>m</i> &le; 300；</p>
<p>对于100%的数据，2 &le; <i>n</i> &le; 1000，1 &le; <i>m</i> &le; 5000。</p>